package com.yoshino.leetcode.oneHundred.twentythreeth;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int majorityElement1(int[] nums) {
        int n = nums.length, mid = n / 2;
        Map<Integer, Integer> maps = new HashMap<>();
        for (int i = 0; i < mid; i++) {
            maps.put(nums[i], maps.getOrDefault(nums[i], 0) + 1);
        }
        for (int i = mid; i < n; i++) {
            int tot = maps.getOrDefault(nums[i], 0) + 1;
            if (tot > mid) {
                return nums[i];
            } else {
                maps.put(nums[i], tot);
            }
        }
        return 0;
    }

    public int majorityElement2(int[] nums) {
        // 超过半数及代表，中位数一定是该数字
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    public int majorityElement(int[] nums) {
        int count=1;//超过半数的一定会有数多余
        int num=nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]==num){
                count++;
            }else if(count>1){
                count--;
            }else {
                num=nums[i];
                count=1;
            }
        }
        return num;
    }

    public int[] constructArr(int[] a) {
        // 左右两边分别累乘
        int[] b = new int[a.length];
        for (int i = 0, temp = 1; i < a.length;temp *= a[i++]) {
            b[i] = temp;
        }
        for (int i = a.length - 1, temp = 1; i >= 0 ;temp *= a[i--]) {
            b[i] *= temp;
        }
        return b;
    }
}